# -*- coding: utf-8 -*-

"""673. 最长递增子序列的个数
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。

示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示: 
1 <= nums.length <= 2000
-10^6 <= nums[i] <= 10^6"""

class Solution:
    """
    这道题先要求到达每个元素的最大距离，然后把最大距离的数目数一下就可以了。
    递归定义： f(i) = max(f(j)+1)         # 0 < j < i 且 nums[j] < nums[i]
    递归基础： f(i) = 1
    然后在最大距离子序列基础上，还要计算最大距离的路径条数
    递归定义: g(i) = sum(g(j))            # 0 < j < i 且 nums[j] < nums[i] 且 g(j) 为前导最大距离
    """
    def findNumberOfLIS(self, nums: list) -> int:
        dp = [1 for _ in range(len(nums))]
        i = 1
        while i < len(nums):
            j = 0
            while j < i:
                if nums[j] < nums[i]:
                    dp[i] = max(dp[j]+1, dp[i])
                j += 1
            i += 1

        ndp = [0 for _ in range(len(nums))]
        i = 0
        while i < len(nums):
            if dp[i] == 1:
                ndp[i] = 1
            else:
                lis = dp[i] - 1
                j = 0
                while j < i:
                    if nums[j] < nums[i] and dp[j] == lis:
                        ndp[i] += ndp[j]
                    j += 1
            i += 1

        lis = max(dp)
        i, n = 0, 0
        while i < len(nums):
            if dp[i] == lis:
                n += ndp[i]
            i += 1

        return n

if __name__ == '__main__':
    rs = Solution().findNumberOfLIS([2,2,2,2,2])
    print(rs)
